\documentclass{sig-alternate} %% Tighter format
%\documentclass{acm_proc_article-sp}
\usepackage{latexsym}

\usepackage{amsmath,amssymb,pifont,graphicx,epstopdf,float}
\usepackage{comment,epsfig,subfigure,url,latexsym,cite}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{enumerate}
\newcommand{\squish}{
        \setlength{\topsep}{0pt}
        \setlength{\itemsep}{0ex}
        \vspace{-1ex}
        \setlength{\parskip}{0pt}}

\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}
\newtheorem{corollary}[lemma]{Corollary}
\newtheorem{theorem}[lemma]{Theorem}

\title{Multi-skill Collaborative Teams based on Densest Subgraphs}
\date{}
\numberofauthors{2}
\author{
\alignauthor
Amita Gajewar \\
	\affaddr{Yahoo! Inc.}\\
	\affaddr{Santa Clara, CA, USA}\\
	\email{amitag@yahoo-inc.com}
\and
\alignauthor
Atish Das Sarma\titlenote{most of the work done while at Georgia Institute of Technology, Atlanta, GA.} \\
       \affaddr{Google Research, Google Inc.}\\
       \affaddr{Mountain View, CA, USA}\\
       \email{dassarma@google.com}
}
%\author{%
%% author names are typeset in 11pt, which is the default size in the author block
%{Amita S. Gajewar{\small $~^{\#1}$}, Atish Das Sarma{\small $~^{*2}$} }%
%% add some space between author names and affils
%\vspace{1.6mm}\\
%\fontsize{10}{10}\selectfont\itshape
%$~^{\#}$Yahoo! Inc.\\
%701 1st Ave, Sunnyvale, CA-94089, USA\\
%\fontsize{9}{9}\selectfont\ttfamily\upshape
%$~^{1}$amitag@yahoo-inc.com
%% add some space between email and affil
%\vspace{1.2mm}\\
%\fontsize{10}{10}\selectfont\rmfamily\itshape
%$~^{*}$College of Computing, Georgia Institute of Technology\\
%266 Ferst Dr., Atlanta, GA-30332, USA\\
%\fontsize{9}{9}\selectfont\ttfamily\upshape
%$~^{2}$atish@cc.gatech.edu
%}

\begin{document}

\conferenceinfo{WWW'11,} {March 28--April 1, 2011, India.} 
\CopyrightYear{2011}
%\crdata{978-1-60558-889-6/10/02} 
% HOW TO GET ABOVE crdata??

\maketitle

\begin{abstract}
We consider the problem of identifying a team of skilled individuals for collaboration, in the presence of a social network. Each node in the input social network may be an expert in one or more skills - such as theory, databases or data mining. The edge weights specify the affinity or collaborative compatibility between respective nodes. Given a project that requires a set of specified number of skilled individuals in each area of expertise, the goal is to identify a team that maximizes the collaborative compatibility. For example, the requirement may be to form a team that has at least three databases experts and at least two theory experts.

The problem we study generalizes the past work of Lappas et al. [KDD '09] where only one individual of each required skill was desired in the team. Further, we explore team formation where the collaborative compatibility objective is measured as the density of the induced subgraph on selected nodes. This measure turns out to be more robust in certain aspects, compared to the previously suggested measures. This problem is NP-hard even when the team requires individuals of only one specific skill. We present a 3-approximation algorithm that improves upon a naive extension of the previously known algorithm for densest at least $k$ subgraph problem. We further show how the same approximation can be extended to the case of multiple skills as well. We also present similar results for a generalization of the previously suggested diameter based objective.

Experiments are performed on a crawl of the DBLP graph where individuals can be skilled in at most four areas - theory, databases, data mining, and artificial intelligence. In addition to our main algorithm, we also present and implement heuristic extensions to trade off between the size of the output and the induced density. These outperform the diameter based objective in identifying strongly cohesive teams of skilled individuals. The results also suggest solutions that are intuitively meaningful and scale well with the increase in the number of skilled individuals required. 
\end{abstract}

%\keywords{Team Formation, Social Networks, Density, Algorithms, Graphs}

\graphicspath{{../version8/plots/}}

\input{introduction}

\input{relatedwork}

\input{problemdef}

\input{densityobjective}

\input{diameterobjective}

\input{experiments}

\input{futurework}

%\input{conclusions}

{\scriptsize
\bibliographystyle{abbrv}
\bibliography{teamofexperts7}
}

\end{document}